1. Field of the Invention
The invention relates to a method of managing scheduled transfers, and more specifically to a method of linking lists of scheduled transfers, especially for serial bus transfers.
2. Description of the Related Art
Computer systems are becoming ever more powerful with each passing moment. Many new advanced bus structures such as the PCI or Peripheral Component Interconnect bus have been developed to allow greater performance of the computer system. Additionally, new devices and uses are being developed for the computer systems. In the past the computer has been essentially a stand-alone device or networked with other computer systems. However, today the modern personal computer is becoming a much more connected and multimedia oriented system. For example, now high speed video and audio functions are becoming commonplace and the integration with the telephone system has already begun.
However, many of these new features and existing devices such as the keyboard, mouse and serial and parallel ports are well below the ultimate bandwidth or capability of the advanced buses such as the PCI bus. Therefore, it is not efficient to connect each one of the functions and devices to the PCI bus directly, as this would impact bus loading and greatly increase overall costs. Additionally, many of these new functions are essentially serial in nature, with the data transferred in a bit stream rather than over a parallel bus structure. This is provided for many reasons, such as reduced wiring costs, and can be done because of the lower data rates which are required.
Therefore, it has been proposed to develop a serial bus architecture to connect all of these various lower bandwidth devices. The universal serial bus (USB) is organized with a host controller (HC) having a series of ports, which can then be connected either directly to devices or functions or to further hubs which have below them further devices or functions. A hub or the host controller may in addition incorporate functions if desired. In this manner a tree structure can be developed to allow a reasonable number of functions or devices to be attached to the serial bus system.
The host controller connects to a bus in the computer system, for example the PCI bus. It is desirable for the bus to support 32 bit addressing, bus mastering and guaranteed access latency. By having the host controller act as a concentrator, only a single connection to the PCI bus is necessary. The connection is better able to utilize the performance of the PCI bus without requiring numerous connections. The host controller, each hub, and each function or port contain particular control registers and control logic for doing set up and initialization operations.
The USB devices are accessed by a unique USB address. Each USB device additionally supports one or more endpoints with which the computer system may communicate.
Four basic types of data transfers are defined in the USB system. The first type is isochronous transfers, which are characterized as periodic, continuous communication between host and device typically used for time-sensitive data/control, such as telephony information or audio information. The second type is bulk transfers, which is characterized by non-periodic, large bursty communication typically used for transfers that can be delayed until bus band width is available, such as printer operations and conventional serial port operations. The third type is control transfers, which are characterized by bursty, non-periodic, host software initiated requests/response communications typically used for command/status operations. The fourth type of transfer, called interrupt transfers, are characterized as small bursty, non-periodic, low frequency, device-initiated communications typically used to notify the host of device service needs, such as is required for keyboard, mouse, pointing device and pen interfaces.
Information is broadcast over the USB from the host controller in a series of packets, with the host controller acting as the bus master and hubs and devices only responding upon request or polling access of the host controller. The packet types include data packets, token packets for use from host to device, a handshake packet and a special control packet. Data packets are the isochronous, asynchronous block, and asynchronous control types. Token packets allow transfer of data packets. Handshake packets are used to perform a ready handshake after transfer of a data or control packet to acknowledge successful receipt or indicate unsuccessful receipt. Special control packets are used for logical reset and status request transfers. Packets are scheduled into queues for transmission over the serial bus in a time division multiplexed fashion.
Each USB transaction begins when the host controller, on a scheduled basis, send a USB packet describing the type of transfer, the USB device address and the endpoint number. This packet is the token packet. The USB device that is addressed selects itself by decoding the appropriate address fields. In a given transaction, data is transferred either from the host to a device or from a device to the host. The direction of data transfer is specified in the token packet. The source of the transfer then sends a data packet or indicates it has no data to transfer. The destination responds with a handshake packet indicating whether the transfer was successful.
Each device and port on a hub or the host controller includes the capabilities to handle the low level bus transfer protocol between the particular node of the appropriate hub and the device itself. Thus, a relatively simple transfer protocol, with a limited number of packet types is defined. More details on the serial bus architecture are provided in the Universal Serial Bus Specification 0.9, dated Mar. 20, 1995, available from Intel Corp. This specification is hereby incorporated by reference.
The computer system communicates to the USB devices via hardware and software layers and interfaces. The host controller and USB devices are primarily hardware based with the USB devices connecting to the host controller in the manner described above. A host controller driver (HCD) and USB driver are primarily software based and provide the software portion of the architecture. The host controller is responsible for communicating information between the host controller driver and the USB devices. The host controller driver is responsible for communicating information between the USB driver and the host controller. A host controller interface (HCI) is the bridge between software (HCD) and hardware (HC).
The USB does not provide a mechanism for attached devices to arbitrate for use of the bus. As a consequence, arbitration for use of the serial bus is "predictive" with the host controller and host software assigned the responsibility of providing service to devices when it is predicted that a device will need it. Usage of the serial bus varies widely among the different data transfer types (isochronous, interrupt, bulk and control) making the task of managing transfers and memory difficult.
Additionally, interrupts on the USB are controlled by the host controller. Each frame, a list of devices to be polled for interrupts is traversed. The host controller issues a token packet to the device wherein if the device needs servicing it can respond to the token packet, thereby initiating an interrupt. Since devices have different servicing requirements, only certain devices are polled each frame. Other devices may be polled much less frequently. When interrupts have been serviced, the interrupt is removed from the list.
Thus, it is anticipated that the transfer lists and the interrupt list may vary greatly from one frame to another. As a result, the overhead from managing these lists and the related memory space requirements will vary from frame to frame. Therefore, it is desirable to provide simplified data structures to the host controller thereby simplifying the operation of the host controller, minimizing memory access and size requirements and providing a simple method of adding and removing devices from the servicing lists.